home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / DiskUtil / Crunch / XPK / DOCS / RDCN.DOC < prev    next >
Text File  |  1993-05-10  |  10KB  |  204 lines
  1.  
  2.                                    RDCN
  3.  
  4.          An implementation of Ross Data Compression for the Amiga
  5.                                  Featuring
  6.                     Fast compression and decompression
  7.                       The fastest overall xpk-library
  8.  
  9.  
  10.             Some copyright 1992, Niklas Sjöberg, but totally PD
  11.  
  12.  
  13.                        History at bottom of file
  14.  
  15.  
  16. LEGAL STUFF
  17. ~~~~~~~~~~~
  18. This library (xpkRDCN.library) may be freely disributed with any kind of
  19. software, as long as no profit is made of the other software. Also, ALL
  20. files, source, docs and binary, must be in the same package. If RDCN is put
  21. in the xpkdev-/xpkusr-archives, source and binary may be splitted.
  22.  
  23. The author takes NO RESPONSABILITY for any damage of lost data caused by
  24. this library. The actual algorithm is 100% OK but bugs may have sneaked
  25. into the code. RDCN have been tested on more than 100Mb of data and have been
  26. compared to the original files. No differences where found. However crunched
  27. data is always more dangerous to use than uncrunched data. It just takes one
  28. single bit that is faulty to make a large part, or even the whole file,
  29. useless.
  30.  
  31. The actual algorithm (in this version) is (c) Ed Ross, see bottom of file.
  32.  
  33.  
  34. WHY? and WHAT IS RDCN?
  35. ~~~~~~~~~~~~~~~~~~~~~~
  36. RDCN is based on a very simple, but yet effective AND fast algorithm published
  37. in `The C Users Journal` Oct '92. It was transferred to Amiga assembly code by
  38. me, since I lacked a both-way fast xpk-packer. The assembly code has been very
  39. much optimized and I think that higher CPS-rates won't be possible if the RDC
  40. method is used. For all you that are interested in compression-stuff:
  41.  
  42. RDCN works with 65K (approx) inbuffers. It also allocates a hash-table of
  43. 4096 entries (that's 16 Kb). Before each 'sequence' RDCN stores a control-
  44. word, in order to distinguish compressed bytes from uncompressed ones. A bit
  45. which is zero indicates that the next byte is uncompressed. Just to be
  46. compatible with the original RDC, RDCN uses bit 15 as byte1-indicator, bit
  47. 14 as byte2 indicator etc. etc. Now, how do the data get compressed? :)
  48.  
  49. o First RDCN checks if the next inbyte equals to the current. If so, get next
  50.   byte, see if that equals to the next etc. etc. RDCN also makes sure that we
  51.   don't advance >4113 bytes.
  52. o If at least 3 bytes were identical, we can use RLE (Run Length Encoding)
  53.   o Were there <19 characters repeated?
  54.     o Yes! This is a short RLE. Since there were at least 3 repeated bytes
  55.       we subtract 3 from the number of repeated bytes. Gee! Max number of
  56.       repeated bytes is now 15, 4 bits. The other four bits (in this case
  57.       zero) tells RDCN which compression method that was used. Next we store
  58.       first the crunched byte (4 bit code, 4 bit 'count') and next the byte
  59.       to be repeated.
  60.       Jump to top.
  61.   o No! We need to use more than one byte for compression code and 'count'.
  62.       Subtract 19 from count. Since we made sure that number of repeated chars
  63.       was less than 4114 we now only need 12 bits for count. Set the 4 bit
  64.       compression-code to 1, store that 4 bits + 4 bits of count. Store 8
  65.       bit count and the byte to repeat.
  66.       Jump to top.
  67. o We found no repeating characters. Use the sliding dictionary instead.
  68.   Calculate a hash between 0 and 4095. Look in dictionary at offset 'hash'.
  69.   (The hash is calculated by using the current byte and the two following)
  70.   Get possible pointer and store the new one (the current position) 
  71. o See if the old pointer in hash_table[hash] wasn't zero!
  72.   o No! Sorry, nothing do to. Just copy the current byte to outbuffer.
  73.     Jump to top.
  74.   o Yes! First make sure the three byte sequence isn't located > 4098 bytes
  75.     away. If it is, we can't compress! ('gap' only uses 12 bits)
  76.     Now, start comparing our current bytes in source to the 'old' bytes which
  77.     hash_table[hash] pointed to. If >271 bytes equal we stop since we can't
  78.     handle longer patterns than 271 bytes (max 8 bits in count).
  79.     o Next, if less than 3 bytes didn't match, we can't compress. Copy current
  80.       byte to outbuffer and jump to top.
  81.     o Did at least three bytes match, but no more than 15?
  82.       o Yes! A short pattern. Combine count (4 bits) with 4 bits from 'gap'
  83.         (gap is the offset from last pattern to current pattern). Next store
  84.         8 more bits from gap (we have subtracted three from gap since at
  85.         least three bits matched and gap can thus be as large as 4098 bytes).
  86.       o No! Encode this as a long pattern. This pattern is at least 16 bytes
  87.         long, so subtract 16 from count. Since we made sure the pattern was no
  88.         longer than 271 bytes we only need 8 bits for count. Gap still need
  89.         12 bits, so combine 4 of them with the four control bits (which are
  90.         set to 2!), store the next 8 gap-bits and last the 8 bit count.
  91. o We're done! Proceed with a jump to top to search for RLE on next source
  92.   byte.
  93.  
  94. To sum up :
  95.  ______________________________________________________________
  96. |Type          |       Byte 1       |    Byte 2   |   Byte 3  |
  97.  --------------------------------------------------------------
  98. |Short RLE     | 0 |  count         | character   | not used  |
  99.  --------------------------------------------------------------
  100. |Long  RLE     | 1 |  low count     | high count  | character |
  101.  --------------------------------------------------------------
  102. |Long  Pattern | 2 |  low offset    | high offset | count     |
  103.  --------------------------------------------------------------
  104. |Short Pattern | 3-15 |  low offset | high offset | not used  |
  105.  ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
  106.  
  107. Have a look at the source. If you find a smart way to speed it up PLEASE
  108. do it and release both binary and cource code into the public domain!!
  109. Improving compression a bit wouldn't be that hard. Even though RDCN compress
  110. fairly well, we really could use BLZW instead (even though it unpacks slow!).
  111. Compression rate isn't the most important thing here, we want speed! :)
  112.  
  113. USAGE:
  114. ~~~~~~
  115. Most of you probably skipped to this section directly :)
  116. RDCN packs fairly well, about 32 % on AmigaVision executable, about
  117. 45-50% on textfiles. On really simple textfiles, like a 'list dh0: ALL' RDCN
  118. may manage to pack upto a CF of 70-80%. On _really_ redundant data, like a
  119. a file full of zeroes RDCN should packs as good as any RLE-packer.
  120.  
  121. The main intention with this packer is 'to go where no packer ever has gone
  122. before' :) Since RDCN is optimized on both packing and depacking it is
  123. intended for devices/dirs you _normally_ wouldn't pack. A C-programming device
  124. would be a good example. It takes a lot of space, data is fairly simple and
  125. you want a decent access speed. However, until a real version of XFH is
  126. released (one which doesn't copy file, wait until it is closed and the packs
  127. it, but rather pack chunks) you may want to wait with the most speed demanding
  128. devices.
  129.  
  130. Since I don't have 'xBench' I've timed BLZW and NUKE a couple of times
  131. and compared them to RDCN (timed using the built-in function in Csh).
  132.  
  133. Method   Packing   Unpacking   Packing   Unpacking   Compression
  134.          Memory     Memory      Speed      Speed        Ratio
  135. ------   -------   ---------   -------   ---------   -----------
  136.  RDCN      16K        0K        180 K/s    800 K/s       33.0%   ; binary
  137.  RDCN      16K        0K        180 K/s    800 K/s       45.0%   ; text
  138.  
  139. When packing all the programs/files in the SAS/C 6.1 package RDCN reduced
  140. size by 42%.
  141.  
  142.  
  143. A more interesting benchmark:
  144.  
  145. FILE: Fish contents 1-650 (some disk missing :-() + AmigaVision executable
  146. FILESIZE: 1725 Kb (ie. around 1766400 bytes)
  147. LOCATION: RAM:
  148. MACHINE: A3000/25 w SCRAM
  149.  
  150. METHOD        PACKTIME    DEPACKTIME    RATIO
  151. NUKE        44.36 secs    4.92 secs    54 %
  152. BLZW.60        13.34 secs    6.70 secs    46 %
  153. *RDCN        11.24 secs    4.34 secs    41 % (old 1.3 version)
  154. RDCN            09.12 secs      3.48 secs       41 % (new 2.1 version)
  155.  
  156. Since NUKE depacks 630 Kb/sec this would indicate that RDCN manages speeds
  157. above 890 Kb/sec. (if NUKE packspeed was compared to RDCN 175 Kb/sec). If
  158. we compare to BLZW, RDCN unpacks 700 Kb/sec. Packing compared to BLZW is
  159. 200 Kb/sec.
  160.  
  161. Well, as I said, I don't have access to xBench, but several other tests shows
  162. that RDCN unpacks more than 800 Kb/sec and generally packs more than 190
  163. Kb/sec.
  164.  
  165.  
  166. BUGS
  167. ~~~~
  168. SAS/C LibVersion and LibRevision are bugged or my c:version stopped working!
  169. version libs:compressors/xpkRDCN.library     -> "version 1.0"
  170. version dh0:libs/compressors/xpkRDCN.library -> "2.1"
  171.  
  172. Any suggestions? (have I missed a keyword in SAS/C or something?)
  173.  
  174. CREDITS
  175. ~~~~~~~
  176. Ed Ross of Application Software for the actual algorithm. Simple, clear and
  177. fast! Thanks Ed!
  178.  
  179. John Harris (jharris@cup.portal.com) did all the optimizing between V1.3 and
  180. V2.1.
  181.  
  182.  
  183. CONTACT
  184. ~~~~~~~
  185. Suggestions to "Niklas Sjoberg" 2:203/415.3@Fidonet
  186.  
  187. If you find a gate between Internet and Fidonet (many did :):
  188. Niklas.Sjoberg@p3.f415.n203.z2.fidonet.org
  189.  
  190.  
  191. HISTORY CHANGES AND UPDATES
  192. ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  193. V1.0 First working version in C, not public, compiled with SAS/C 6.0
  194. V1.1 Decompression written in assembler, not public
  195. V1.2 Compression written in assembler, not public
  196. V1.3 Small optimizations, first public release, compiled with SAS/C 6.1
  197. V1.4 Fixed 68000-bug (word fetch at odd address, sorry..), never released
  198.      due to the fact that I waited for Stefan Boberg's promised optimizations.
  199. V2.0 Implemented John Harris's new code.
  200. V2.1 Fixed a couple of serious bugs, public release, compiled with SAS/C 6.2
  201. V2.2 (By John Harris) Fixed above bugs in ways that didn't slow down the 
  202.      routine.  Also fixed more 68000 problems and errors in code translation.
  203.      Updated the version strings which had still shown '1.0'.
  204.